package mo.tags.depthfirst;

import mo.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class L99 {

    public void recoverTree(TreeNode root) {
        List<Integer> arr = new ArrayList<>();
        preOrder(root, arr);
        int[] indexes = getIndex(arr);
        int x = arr.get(indexes[0]);
        int y = arr.get(indexes[1]);
        recover(root, 2, x, y);

    }


    private void recover(TreeNode root, int count, int x, int y) {
        if (root == null) {
            return;
        }
        if (root.val == x || root.val == y) {
            root.val = root.val == x ? y : x;
            count--;
            if (count == 0) {
                return;
            }
        }
        recover(root.left, count, x, y);
        recover(root.right, count, x, y);
    }


    private int[] getIndex(List<Integer> arr) {
        int index1 = -1, index2 = -1;
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr.get(i+1) < arr.get(i)) {
                index2 = i+1;
                if (index1 == -1) {
                    index1 = i;
                } else {
                    break;
                }
            }
        }
        return new int[]{index1, index2};
    }


    private void preOrder(TreeNode root, List<Integer> arr) {
        if (root == null) {
            return;
        }
        preOrder(root.left, arr);
        arr.add(root.val);
        preOrder(root.right, arr);
    }


}
